Thuật toán lý thuyết

Reed & Solomon (1960) mô tả một thuật toán giải mã để tìm ra đa thức phù hợp nhất. Thuật toán cho mã RS ( n , k ) {\displaystyle (n,k)} kiểm tra tất cả mọi bộ k {\displaystyle k} ký hiệu trong số n {\displaystyle n} ký hiệu nhận được. Nói chung, để có thể giải mã thì cần nhận được ít nhất k {\displaystyle k} ký hiệu đúng, và đây cũng chính là số ký hiệu cần thiết để nội suy ra đa thức thông điệp. Thuật toán giải mã thử nội suy mọi bộ k {\displaystyle k} ký hiệu và so sánh giá trị của đa thức thu được ở các vị trí khác với giá trị nhận được. Đa thức nào cho giá trị đúng ở nhiều vị trí nhất chính là đa thức thông điệp. Tuy nhiên số tập hợp con gồm k {\displaystyle k} ký hiệu là rất lớn nên thuật toán này không có giá trị thực tiễn. Số tập hợp con là ( n k ) = n ! ( n − k ) ! k ! {\displaystyle \textstyle {\binom {n}{k}}={n! \over (n-k)!k!}} , quá lớn với ngay cả những mã khá nhỏ. Để sửa 3 lỗi của mã ( 255 , 249 ) {\displaystyle (255,249)} , thuật toán phải kiểm tra 359 tỉ tập hợp con.

Thuật toán giải mã Peterson

Peterson (1960) đưa ra một thuật toán giải mã hiệu quả dựa trên giải mã hội chứng. Berlekamp sau đó đã cải tiến thuật toán này (mô tả dưới đây).[4]

Giải mã hội chứng

Có thể xem thông điệp gửi đi là các hệ số của một đa thức s(x) chia hết cho đa thức sinh g(x).[5]

s ( x ) = ∑ i = 0 n − 1 c i x i {\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}} g ( x ) = ∏ j = 1 n − k ( x − α j ) , {\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}

trong đó α là một căn nguyên thủy của đơn vị.

Vì s(x) chia hết cho g(x), nên

s ( α i ) = 0 ,   i = 1 , 2 , … , n − k {\displaystyle s(\alpha ^{i})=0,\ i=1,2,\ldots ,n-k}

Đa thức truyền đi được cộng thêm một đa thức lỗi e(x) để tạo thành đa thức nhận được r(x).

r ( x ) = s ( x ) + e ( x ) {\displaystyle r(x)=s(x)+e(x)} e ( x ) = ∑ i = 0 n − 1 e i x i {\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}

Trong đó ei là hệ số của lũy thừa bậc i của x. Hệ số ei bằng không nếu không có lỗi ở vị trí i và khác không nếu có lỗi. Nếu có lỗi ở ν lũy thừa khác nhau ik của x, thì

e ( x ) = ∑ k = 1 ν e i k x i k {\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}}

Mục tiêu của thuật toán là tìm ra ν, các vị trí ik, và giá trị lỗi ở các vị trí đó.

Định nghĩa các hội chứng Sj như sau

S j = r ( α j ) = s ( α j ) + e ( α j ) = 0 + e ( α j ) = e ( α j ) ,   j = 1 , 2 , … , n − k = ∑ k = 1 ν e i k ( α j ) i k {\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})=e(\alpha ^{j}),\ j=1,2,\ldots ,n-k\\&=\sum _{k=1}^{\nu }e_{i_{k}}\left(\alpha ^{j}\right)^{i_{k}}\end{aligned}}}

Lợi thế của việc xét các hội chứng là chúng chỉ phụ thuộc vào đa thức lỗi, không phụ thuộc thông điệp.

Định vị lỗi và giá trị lỗi

Định nghĩa định vị lỗi Xk và giá trị lỗi Yk như sau:

X k = α i k ,   Y k = e i k {\displaystyle X_{k}=\alpha ^{i_{k}},\ Y_{k}=e_{i_{k}}}

Khi đó có thể viết các hội chứng bằng định vị lỗi và giá trị lỗi như sau:

S j = ∑ k = 1 ν Y k X k j {\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}}

Các hội chứng cho ta n − k ≥ 2ν phương trình trên 2ν ẩn, nhưng các phương trình này không tuyến tính theo Xk và có thể khó giải. Tuy nhiên nếu đã biết Xk thì hệ các phương trình hội chứng là một hệ phương trình tuyến tính của các giá trị lỗi Yk và có thể giải dễ dàng.

[ X 1 1 X 2 1 ⋯ X ν 1 X 1 2 X 2 2 ⋯ X ν 2 ⋮ ⋮ ⋮ X 1 n − k X 2 n − k ⋯ X ν n − k ] [ Y 1 Y 2 ⋮ Y ν ] = [ S 1 S 2 ⋮ S n − k ] {\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &&\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}}}

Vì vậy vấn đề chính là tìm ra Xk.

Đa thức định vị lỗi

Peterson tìm ra một quan hệ truy toán tuyến tính dẫn đến một hệ phương trình tuyến tính. (Welch 1997, tr. 10)Nếu giải hệ này thì có thể tìm ra các định vị lỗi.

Định nghĩa đa thức vị trí lỗi Λ(x) như sau

Λ ( x ) = ∏ k = 1 ν ( 1 − x X k ) = 1 + Λ 1 x 1 + Λ 2 x 2 + ⋯ + Λ ν x ν {\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }}

Các nghiệm của Λ(x) là các nghịch đảo của X k − 1 {\displaystyle X_{k}^{-1}} :

Λ ( X k − 1 ) = 0 {\displaystyle \Lambda (X_{k}^{-1})=0} Λ ( X k − 1 ) = 1 + Λ 1 X k − 1 + Λ 2 X k − 2 + ⋯ + Λ ν X k − ν = 0 {\displaystyle \Lambda (X_{k}^{-1})=1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu }=0}

Nhân cả hai vế với Y k X k j + ν {\displaystyle Y_{k}X_{k}^{j+\nu }} và giá trị nhận được vẫn là 0.

Y k X k j + ν Λ ( X k − 1 ) = 0. N e ^ n  Y k X k j + ν + Λ 1 Y k X k j + ν X k − 1 + Λ 2 Y k X k j + ν X k − 2 + ⋯ + Λ ν Y k X k j + ν X k − ν = 0 , hay  Y k X k j + ν + Λ 1 Y k X k j + ν − 1 + Λ 2 Y k X k j + ν − 2 + ⋯ + Λ ν Y k X k j = 0 {\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0.\\{\text{N}}{\hat {\mbox{e}}}{\text{n }}&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\{\text{hay }}&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0\\\end{aligned}}}

Cộng các đẳng thức trên cho k = 1 đến ν

∑ k = 1 ν ( Y k X k j + ν + Λ 1 Y k X k j + ν − 1 + Λ 2 Y k X k j + ν − 2 + ⋯ + Λ ν Y k X k j ) = 0 ∑ k = 1 ν ( Y k X k j + ν ) + Λ 1 ∑ k = 1 ν ( Y k X k j + ν − 1 ) + Λ 2 ∑ k = 1 ν ( Y k X k j + ν − 2 ) + ⋯ + Λ ν ∑ k = 1 ν ( Y k X k j ) = 0 {\displaystyle {\begin{aligned}&\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0\\&\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu })+\Lambda _{1}\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu -1})+\Lambda _{2}\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu -2})+\cdots +\Lambda _{\nu }\sum _{k=1}^{\nu }(Y_{k}X_{k}^{j})=0\end{aligned}}}

Rút gọn đẳng thức trên, ta thu được

S j + ν + Λ 1 S j + ν − 1 + ⋯ + Λ ν − 1 S j + 1 + Λ ν S j = 0 {\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0\,} S j Λ ν + S j + 1 Λ ν − 1 + ⋯ + S j + ν − 1 Λ 1 = − S j + ν   {\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }\ }

Đây là một hệ phương trình tuyến tính mà giải nó cho ta các hệ số Λi của đa thức định vị lỗi:

[ S 1 S 2 ⋯ S ν S 2 S 3 ⋯ S ν + 1 ⋮ ⋮ ⋮ S ν S ν + 1 ⋯ S 2 ν − 1 ] [ Λ ν Λ ν − 1 ⋮ Λ 1 ] = [ − S ν + 1 − S ν + 2 ⋮ − S ν + ν ] {\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &&\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}}

Tìm định vị lỗi từ đa thức định vị lỗi

Từ các hệ số Λi tìm được ở bước trên, ta thu được đa thức định vị lỗi. Có thể tìm các nghiệm của đa thức định vị lỗi bằng các thử tất cả mọi giá trị có thể. Có thể tính các định vị lỗi (và do đó các vị trí lỗi) từ các nghiệm. Tìm kiếm Chien là một thuật toán hiệu quả cho bước này.

Tính giá trị lỗi

Sau khi đã tìm ra các vị trí lỗi, có thể tìm ra các giá trị lỗi và sửa chúng. Có thể giải hệ phương trình ở trên để tính Yk, hoặc dùng thuật toán Forney.

Thuật toán Berlekamp–Massey

Thuật toán Berlekamp–Massey là một thuật toán lặp để tìm lỗi. Trong mỗi lần lặp, thuật toán tính một giá trị sai lệch dựa trên giá trị hiện thời của Λ(x) và số lượng lỗi giả định e:

Δ = S i + Λ 1   S i − 1 + ⋯ + Λ e   S i − e {\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}

sau đó điều chỉnh Λ(x) và e sao cho giá trị Δ bằng không. Xem mô tả chi tiết thủ tục lặp ở thuật toán Berlekamp–Massey. Trong ví dụ dưới đây, C(x) được dùng để biểu diễn Λ(x).

Ví dụ

Xét mã Reed–Solomon định nghĩa trên GF(929) với α = 3 và t = 4 (mã này thường dùng cho mã vạch PDF417). Đa thức sinh là

g ( x ) = ( x − 3 ) ( x − 3 2 ) ( x − 3 3 ) ( x − 3 4 ) = x 4 + 809 x 3 + 723 x 2 + 568 x + 522 {\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522}

Nếu đa thức thông điệp là p(x) = 3 x2 + 2 x + 1, thì mã tự nhận giá trị sau.

s r ( x ) = p ( x ) x t mod g ( x ) = 547 x 3 + 738 x 2 + 442 x + 455 {\displaystyle s_{r}(x)=p(x)\,x^{t}\mod g(x)=547x^{3}+738x^{2}+442x+455} s ( x ) = p ( x ) x t − s r ( x ) = 3 x 6 + 2 x 5 + 1 x 4 + 382 x 3 + 191 x 2 + 487 x + 474 {\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474}

Lỗi trong quá trình truyền có thể khiến cho đa thức nhận được trở thành

r ( x ) = s ( x ) + e ( x ) = 3 x 6 + 2 x 5 + 123 x 4 + 456 x 3 + 191 x 2 + 487 x + 474 {\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474}

Các hội chứng là các giá trị của r tại các lũy thừa của α.

S 1 = r ( 3 1 ) = 3 ⋅ 3 6 + 2 ⋅ 3 5 + 123 ⋅ 3 4 + 456 ⋅ 3 3 + 191 ⋅ 3 2 + 487 ⋅ 3 + 474 = 732 {\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732} S 2 = r ( 3 2 ) = 637 , S 3 = r ( 3 3 ) = 762 , S 4 = r ( 3 4 ) = 925 {\displaystyle S_{2}=r(3^{2})=637,\;S_{3}=r(3^{3})=762,\;S_{4}=r(3^{4})=925}

Để sửa lỗi, dùng thuật toán Berlekamp–Massey để tính đa thức định vị lỗi.

n	Sn+1	d	C	B	b	m
0	732	732	197 x + 1	1	732	1
1	637	846	173 x + 1	1	732	2
2	762	412	634 x2 + 173 x + 1	173 x + 1	412	1
3	925	576	329 x2 + 821 x + 1	173 x + 1	412	2

Giá trị cuối cùng của C là đa thức định vị lỗi, Λ(x). Có thể tìm các nghiệm bằng cách thử mọi giá trị. Các nghiệm là x1 = 757 = 3−3 và x2 = 562 = 3−4, ứng với các vị trí lỗi. Để tìm ra giá trị lỗi, áp dụng thuật toán Forney.

Ω ( x ) = S ( x ) Λ ( x ) mod x 4 = 546 x + 732 {\displaystyle \Omega (x)=S(x)\Lambda (x)\mod x^{4}=546x+732\,} Λ ′ ( x ) = 658 x + 821 {\displaystyle \Lambda '(x)=658x+821\,} e 1 = − Ω ( x 1 ) / Λ ′ ( x 1 ) = − 649 / 54 = 280 × 843 = 74 {\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=-649/54=280\times 843=74\,} e 2 = − Ω ( x 2 ) / Λ ′ ( x 2 ) = 122 {\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122\,}

Trừ e1x3 và e2x4 từ đa thức nhận được r để tìm ra mã tự ban đầu s.